#include <iostream>
#include <vector>

using namespace std;

//# 法三：双指针分区（lomuto原理类似）
void sortColors3(vector<int>& nums) {
        int p0 = 0, p1 = 0;
        for(int i = 0; i<nums.size(); i++){
            if(nums[i]==0){
                swap(nums[p0], nums[i]);
                if(p0<p1){
                    //当p0<p1时，说明p0处是1，前一步的交换会将这个1换走
                    //我们需要将这个1再换到合适的位置上，也就是p1处
                    swap(nums[p1], nums[i]);
                }
                p0++;
                p1++;
            }else if(nums[i]==1){
                swap(nums[p1], nums[i]);
                p1++;
            }
        }
}

// # 法二：Lomuto快排
    int partition(vector<int>& nums, int left, int right){
        int k = nums[right];
        int i = left - 1, j = left;
        for(; j < right; j++){
            if(nums[j] < k){
                i++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i+1], nums[j]);
        return i+1;
    }
    void quick_sort(vector<int>& nums, int left, int right){
        if(left<right){
            int q = partition(nums, left, right);
            quick_sort(nums, left, q-1);
            quick_sort(nums, q+1, right);
        }
    }
    void sortColors2(vector<int>& nums) {
        quick_sort(nums, 0, nums.size()-1);
    }